perm filename M[144,DBL] blob
sn#024234 filedate 1973-02-08 generic text, type T, neo UTF8
00100 SOFAR EQU 2000 ;LINEAR LIST: THE iTH LOCATION GIVES THE ADDRESS
00200 PROBUFF EQU 2300 ;PRODUCTIONS ARE STORED SEQUENTIALLY,BEGINNING HERE.
00300 * THAT THE iTH STRING1 BEGINS IN.
00400 LINK EQU 4:5 ;THE LINK BYTES OF A MAIN STRING NODE.
00500 READER EQU 16
00600 PRINTER EQU 18
00700 NEXTPRO EQU 5 ;THE NO. OF WORDS ALLOTTED TO EACH PRODUCTION.
00800 1STCHAR EQU 1:1 ;FIELD SPECIFICATION FOR LEFTMOST BYTE.
00900 FIELDBY EQU 4:4 ;THE BYTE IN AN INSTRUC. THAT THE
01000 * FIELD SPEC. GOES INTO.
01100 NXTCHAR EQU 1:1 ;ADD THIS TO THE FIELD SPEC.
01200 * TO ADDRESS THE NEXT BYTE.
01300 FINLBUF EQU 3900 ;THE FINAL OUTPUT BUFFER FOR MAIN
01400 CONTENT EQU 1:1 ;THE BYTES OF A MAIN NODE THAT CONTAIN THE
01500 * ACTUAL CHAR. CODE, THE NODE'S CONTENTS.
01600 MAXSLEN EQU 10 ;THE MAX. NO. OF CHARS. IN ANY STRING1 OR STRING2.
01700 BLANK EQU 0 ;THE CODE FOR A WORDFUL OF BLANKS.
01800 STRNG1A EQU 0 ;STRING1 IS STORED IN LOAD(SOFAR + CURRENT rI6)
01900 STRNG1B EQU 1 ; + THESE OFFSETS.
02000 STRNG2A EQU 2 ;STRING2 IS STORED SIMILARY USING THESE
02100 STRNG2B EQU 3 ; OFFSETS.
02200 LABEL2 EQU 4 ;SIMILARLY, THIS IS THE OFFSET FOR LABEL2.
02300 LASTBYT EQU 5:5 ;FIELD SPEC. FOR RIGHTMOST CHARACTER OF WRD.
02400 *
02500 ORIG 1000 ;THE FIRST 1000 LOCS. ARE RESERVED FOR
02600 * MAIN (I.E.,MAINSTRING) NODES.
02700 *
02800 STORE1 CON 0
02900 STORE2 CON 0
03000 STORE3 CON 0
03100 STORE4 CON 0
03150 STORE5 CON 0
03200 STOREA CON 0
03300 FINLBYT CON 5:5 ;SAME AS LASTBYT, BUT USED FOR CMPi OPERATIONS.
03400 MTOP CON 1 ;MARKER TO THE TOP OF THE MAIN LINKED LIST STRUCTURE.
03500 CBOT CON 1 ;OUR FREE STORAGE STARTS AT THIS ADDRESS
03600 AVAIL CON 0 ;OUR LINKED FREE STORAGE STARTS AT THIS ADDRESS.
03700 BLANKS CON 0 ;A WORD OF BLANKS (USED FOR CMPi INSTRUCTIONS.
03800 LFINAL CON 0 ;THE FINAL LINK FIELD IS TEMPORARILY STORED HERE.
03900 TITLE ALF ;TITLE PRINTED AT BEGINNING OF OUTPUT.
04000 ALF
04100 ALF MARKO
04200 ALF V AL
04300 ALF GORIT
04400 ALF HMS
04500 ALF
04600 ALF CS 1
04700 ALF 44A
04800 ALF
04900 ALF
05000 ALF Doug
05100 ALF Lenat
05200 ORIG *+12 ;PAD OUT TITLE LINE WITH BLANKS
05300 LASTPRO CON 0 ;THE HIGHEST LABEL1 READ IN SO FAR.
05400 ENDALG CON 0 ;WHEN LABEL2 IS BLANK, THE ALGORITHM MUST HAVE JUST ENDED.
05500 *
05600 *
05700 START ENT6 PROBUFF ;rI6 HOLDS THE PRODUCTION-STORAGE OFFSET.
05800 ST6 SOFAR,2 ;NOTE THAT THIS PRESUPPOSES rI6 STARTS AT ZERO.
05900 IN 0,6(READER) ;READ IN THE FIRST PRODUCTION.
06000 OUT TITLE(PRINTER) ;PRINT OUT THE OUTPUT HEADING.
06100 JMP GETFNOD ;MAIN WILL NEED AT LEAST ONE FREE NODE, WE ASSUME.
06200 * GETFNOD IS A SUBROUTINE WHICH RETURNS THE ADDRESS
06300 * OF THE NEXT FREE NODE IN rI1.
06400 ST1 MTOP(LINK) ;STORE IS ADDRESS IN TH FIRST LINK FIELD,
06500 ENT4 0,1 ;THAT OF MTOP, AND INTO REGISTER 4 ALSO.
06600 JBUS *(READER) ;WE CAN'T DO ANY MORE UNTIL THE PROD. I READ IN.
06700 LDX LABEL2,6 ;WE CONVERT LABEL2 TO A NUMBER.
06800 NUM ; NOTE: WE ASSUME rA IS ZEROED INITIALLY.
06900 STA LABEL2,6
07000 *
07100 ENT5 MAXSLEN
07200 LDA STRNG2A,6 ;THE STRING2 WILL STAY IN rAX THROUGHOUT THIS
07300 LDX STRNG2B,6 ; UPCOMING LOOP.
07400 XEQ CMPA BLANKS(1STCHAR) ;EXAMINE THE LEFTMOST CHARACTER OF THE STRING.
07500 * WE KNOW THAT PROD. 0 IS APPLICABLE; HERE WE SEE
07600 * IF WE ARE THRU CARRYING IT OUT.
07700 JE CIRCEND ; we are... so jump ahead to CIRCEND.
07800 STA 0,4 ;PUT THE CHAR. INTO THE LAST NODE OF MAIN.
07900 * NOTE: THIS PUTS JUNK IN THE LINK FIELD, BUT WE ARE
08000 * ABOUT TO SET IT ANYWAY.
08100 JMP GETFNOD ;WE WILL IN GENERAL REQUIRE A NEW NODE.
08200 ST1 0,4(LINK) ;SEE, HERE IS WHERE THE LINK FIELD IS SET.
08300 ENT4 0,1 ;REG. 4 NOW POINTS TO THE NEW LAST NODE.
08400 SLAX 1
08500 DEC5 1 ;RECALL THAT REG.5 STARTED WITH MAX.STRING LENGTH.
08600 J5P XEQ ; IF REG.5 IS ZERO, WE MUST BE AT END OF TASK...
08700 CIRCEND LD5 LABEL2,6 ;SEE IF WE CAN GO ON WITHOUT INPUTTING ANYMORE PRODUCTIONS.
08800 GETSET CMP5 LASTPRO ;HAS THE PROD. REQUIED NEXT BEEN READ IN YET?
08900 JLE APPLIC ; yes... see if we can apply it to MAIN.
09000 GS2 LD2 LASTPRO ; no.... we must input some more productions.
09100 LD6 SOFAR,2 ;GET THE OFFSET FOR THE LAST PROD. READ IN INTO rI6
09200 GS3 INC2 1
09300 INC6 NEXTPRO
09400 IN 0,6(READER)
09500 ST6 SOFAR,2
09600 DEC5 1
09700 CMP5 LASTPRO
09800 JBUS *(READER) ;THIS ADDS BUT LITTLE TIME, SINCE EITHER WE MUST
09900 * JUMP BACK TO GS2 RIGHT NOW,
10000 * AND "IN" AGAIN, OR ELSE WE MUST ACCESS THIS JUST-READ-
10100 * IN INFORMATION IN THE APPLIC LOOP A FEW INSTRUCS. LATER.
10200 LDX LABEL2,6 ;WE CONVERT LABEL2 TO A NUMBER.
10300 ENTA BLANK ;THE ACCUMULATOR MUST BE BLANKS.
10400 NUM
10500 STA LABEL2,6
10600 JG GS3
10700 ST2 LASTPRO
10800 ENT5 0,2
10900 APPLIC LD6 SOFAR,5 ;AT THIS POINT, rI5 CONTAINS THE NO. OF THE
11000 * NEXT DESIRED PRODUCTION, AND WE KNOW THAT
11100 JMP FINISHD
11200 * WE HAVE ALREADY READ IT IN.
11300 ENT2 0,5
11400 LDA LABEL2,6 ;SEE WHETHER WE ARE DONE WITH THE ALGORITHM.
11500 CMPA ENDALG
11600 JE ENDIT
11700 ENT5 MTOP
11800 MATCH1 LDA STRNG1A,6
11900 LDX STRNG1B,6
12000 * NOTE THE TRICKY WAY THAT THIS WORKS FOR STRING1=BLANK:
12100 * THE CONTENT FIELD OF MTOP IS BLANKS ALSO...
12200 *
12300 ENT1 0,5
12400 MATCH2 CMPA 0,1(CONTENT) ;DO THE 1ST CHARS. MATCH OR NOT?
12500 JE MAYBE1 ;yes. MAYBE the whole string will: try on!!
12600 MATCH3 LD1 0,1(LINK) ;no. we shall advance along to next node of main.
12650 ST5 STORE5
12700 ENT5 0,1 ;rI5 MARKS THE LAST NODE OF MAIN WHERE A TRIAL-
12800 * MATCH WAS INITIATED.
12900 J1NZ MATCH2 ;IF WE AREN'T AT THE END OF MAIN YET,
13000 INC2 1 ; GO BACK TO MATCH2 AND TRY AGAIN.
13100 ENT5 0,2 ;IF WE ARE AT MAIN'S END,THE PROD. IS INAPPLICABLEE.
13200 JMP GETSET ;WE TRY THE PROD. WITH LABEL1 ONE HIGHER.
13300 *
13400 MAYBE1 ST1 STORE1 ;WE MAY NEED THIS "OLD" VALUE OF rI1.
13500 MAYBE SLAX 1
13600 CMPA BLANKS(CONTENT) ;ARE WE FINISHED WITH THE MATCH?
13700 JE SUCCESS ;YES: JUMP TO SUCCESS AND INSTITUTE THE PROD.
13800 LD1 0,1(LINK) ;NOT YET; PREPARE TO TRY MATCHING THE NEXT
13900 CMPA 0,1(CONTENT) ; CHARS. IN MAIN AND IN STRING1.
14000 JE MAYBE ;THEY MATCH. WE STILL SAY MAYBE ON THE TOTAL MATCH.
14100 LDA STRNG1A,6 ;THEY DON'T MATCH. WE ADVANCE ALONG MAIN AND TRY
14200 LDX STRNG1B,6 ;TO MATCH FIRST CHARACTERS AGAIN. NOTE THATTHE
14300 LD1 STORE1 ;SEE, WE DID NEED TO SAVE THE PREVIOUS rI1 VALUE.
14400 JMP MATCH3 ;ADVANCE IS FROM THE PREVIOUS STARTING POSITION,
14500 * AS HELD BY REG.5, AND NOT FROM THE LAST MAIN
14600 * NODE CONSIDERED, HELD BY REG.1.
14700 * THIS IS RUDIMENTARY BACKTRACKING.
14800 *
14900 SUCCESS LDA STRNG1A,6 ;SEE WHICH STRING IS LONGER, --1 OR --2.
15000 LDX STRNG1B,6
15100 ENT3 0
15200 ENT4 0
15300 LONGER1 CMPA BLANKS(CONTENT)
15400 JE LONGER2
15500 SLAX 1
15600 INC3 1
15700 JMP LONGER1
15800 LONGER2 LDA STRNG2A,6 ;AT THIS POINT, REG. 3 CONTAINS THE LENGTH OF
15900 LDX STRNG2B,6 ; STRING1.
16000 LONGER3 CMPA BLANKS(CONTENT)
16100 JE LONGER4
16200 SLAX 1
16300 DEC3 1
16400 JMP LONGER3
16500 LONGER4 J3Z REPLACE ;rI3 NOW CONTAINS LENGTH(STRING1)-LENGTH(STRING2).
16600 * IF THE LENGTHS ARE EQUAL, ALL WE NEED DO IS REPLACE
16700 * THE CONTENT FIELDS OF SOME NODES.
16800 *
16900 J3P DELSOME ;IF LEN.(STR1) > LEN.(STR2) THEN WE WILL HAVE
17000 * TO DELETE SOME NODES FROM OUR STRUCTURE,
17100 * AND THEN REPLACE SOME OTHERS' CONTENTS.
17200 *
17300 * IF LEN.(STR1) < LEN(STR2) THEN WE WILL HAVE TO
17400 ADDSOME ENT4 0,5 ; INSERT SOME NODES INTO OUR STRUCTURE, AND THEN
17500 LDA 0,4(LINK)
17600 * REPLACE SOME NODES' CONTENT FIELDS.
17700 * IN THE ACCUMULATOR, WE STORE "FINAL" LINK TEMPORARILY.
17800 ADDS2 JMP GETFNOD
17900 ST1 0,4(LINK) ;WE MUST ADD SOME NEW NODES TO THE STRCTURE.
18000 ENT4 0,1 ;UPDATE THE LINK STRUCTRE.
18100 INC3 1 ;THIS IS ONE LESS NODE WE HAVE TO ADD.
18200 J3N ADDS2 ;IF WE STILL HAVE SOME TO ADD, KEEP AT IT.
18300 * WE NOW RETRIEVE THE FINAL LINK, AND
18400 STA 0,4(LINK) ; ADD IT TO THE STRUCTURE.
18500 JMP REPLACE ;WE ONLY HAVE TO REPLACE CONTENTS NOW.
18600 *
18700 DELSOME LD4 STORE5(LINK) ;PRESERVE INITIAL LINK IN REG. 5.
18800 LD1 0,4(LINK)
18900 ST1 LFINAL
19000 DELS2 LD1 LFINAL ;LOAD ADDRESS OF NODE TO BE FREED.
19100 LD4 0,1(LINK)
19200 ST4 LFINAL
19300 JMP SETNODF ;SET IT FREE BY LINKING IT ONTO AVAIL.
19400 DEC3 1 ; LINK STRUCTURE UNTIL ALL DELTEIONS ARE DONE.
19500 J3P DELS2 ;IF WE'VE MORE TO DELETE, KEEP AT IT.
19600 LD3 STORE5(LINK)
19650 ST4 0,3(LINK) ;RESET THE INITIAL LINK FIELD NOW.
19700 * WE NOW JUST HAVE TO REPLACE SOME NODE CONTENTS.
19800 *
19900 REPLACE LDA STRNG2A,6
20000 LDX STRNG2B,6
20100 REPL2 SLC 1
20200 CMPX BLANKS(LASTBYT) ;ARE WE THROUGH TRANSFERRING?
20300 JE CIRCEND ;yes: follow label2 to next production desired.
20400 STX 0,5(CONTENT) ;no: transfer one new char from STRING2 to MAIN.
20500 LD5 0,5(LINK)
20600 JMP REPL2
20700 *
20800 *
20900 FINISHD STJ EF
21000 ST1 STORE1
21100 ST2 STORE2
21200 ST3 STORE3
21300 STA STOREA
21400 ST4 STORE4
21500 ENT1 MTOP ; AT THIS POINT WE HAVE FOLLOWED THE MARKOV
21600 ENT4 0
21700 ENT3 -1 ; ALGORITHM TO COMPLETION. PRINT OUT THE FINAL
21750 JBUS *(PRINTER) ;NOTE THIS DOESN'T ADD TOO MUCH TIME.
21800 F1 ENT2 1STCHAR ; MAINSTRING AND STOP EXECUTION.
21900 INC3 1
22000 F2 LD1 0,1(LINK)
22100 ENTA 0,1
22200 CHAR
22300 STX FINLBUF+26,4(LINK)
22400 INC4 1
22500 LDA 0,1(CONTENT)
22600 ST2 *+1(FIELDBY) ; WATCH OUT: WE ARE MODIFYING THE NEXT INSTRUC.
22700 STA FINLBUF,3 ;THE FIELD SPEC. GETS RESET CONTINUALLY.
22800 J1Z QUIT ;WHEN THE LINK FIELD IS ZERO, WE'VE REACHED THE
22900 INC2 NXTCHAR ; END OF MAIN. OTHERWISE, GET THE NEXT NODE.
23000 CMP2 FINLBYT ;HAVE WE FINISHED PACKING THIS WORD YET??
23100 JLE F2 ;no: continue packing it with the next node contents.
23200 JMP F1 ;yes: reset rI2 (field) and increment rI3 (word).
23300 QUIT OUT FINLBUF(PRINTER) ;NOTE: WHILE MAIN CAN BE AS BIG AS 1000 NODES
23400 * DURING THE EVALUATION OF THE ALGORITHM, THE PROGRAM AS-
23500 * SUMES THAT IT HAS RESHRUNK TO UNDER 121 NODES BY THE END.
23600 ENTA 0,5
23700 CHAR
23800 STX FINLBUF+25
23900 OUT FINLBUF+25(PRINTER)
24100 LD1 STORE1
24200 LD2 STORE2
24300 LD3 STORE3
24400 LD4 STORE4
24500 LDA STOREA
24600 EF JMP *
24700 *
24800 ENDIT JMP FINISHD
24900 HLT
25000 GETFNOD STJ EXITGFN ;THIS SUBROUTINE WAS WRITTEN TO SHOW HOW
25100 LD1 AVAIL(LINK) ; CUMBERSOME PROGRAMMING IS WHEN YOU ARE
25200 J1NZ REUSE ; RESTRICTED TO USING JUST A SINGE REGISTER,
25300 LD1 CBOT ; IN THIS CASE, REGISTER 1.
25400 INC1 1 ; THIS WAS DONE NOT OUT OF NECESSITY BUT OUT OF
25500 ST1 CBOT ; EXAMPLE. SEE THE FOLLOWING SUBROUTINE
25600 DEC1 1 ; SETNODF TO SEE HOW MUCH SUPERIOR TWO REGISTERS
25700 JMP EXITGFN ; ARE IN REDUCING CODE AND MACHINE TIME.
25800 REUSE ST1 TEMP1
25900 LD1 0,1(LINK)
26000 ST1 AVAIL(LINK)
26100 LD1 TEMP1
26200 EXITGFN JMP *
26300 *
26400 *
26500 SETNODF STJ EXITSNF ;THIS SUBROUTINE USES rI1 AND rA.
26600 LDA AVAIL(LINK)
26700 ST1 AVAIL(LINK)
26800 STA 0,1(LINK)
26900 EXITSNF JMP *
27000 *
27100 *
27200 END START